#include <bits/stdc++.h>
using namespace std;

int a,m,phi=1;
int bm,flag;

long long quickpow(long long x,long long y)
{
	long long ans=1;
	while(y!=0)
	{
		if(y%2==1)
		{
			ans=ans*x%m;
		}
		x=x*x%m;
		y=y/2;
	}
	return ans;
}

int main() 
{
	cin >> a >> m;
	a %= m;
	int mm = m;
	for (int i = 2; i * i <= mm; i++) 
	{
		if (mm % i) continue;
		phi *= i - 1;
		mm /= i;
		while (mm % i == 0)
			phi *= i,
			mm /= i;
	} 
	if (mm > 1) phi *= mm - 1;
	
	char ch;
	while ((ch = getchar()) < '0' || ch > '9') ;
	while (bm = bm * 10ll + (ch ^ '0'), (ch = getchar()) >= '0' && ch <= '9')
		if (bm >= phi) flag = 1, bm %= phi;
	if (bm >= phi) flag = 1, bm %= phi;
	if (flag) bm += phi;
	
	cout << quickpow(a,bm) << endl;
	return 0;
}
